查找中位数（分治策略）

设计与实现查找数组的中项问题的算法；

要找出一个数组的中位数，最简单的方法当然是将数组排序，但快速排序的时间复杂度也需要O(nlogn)，我们可以寻找更快的算法来解决。首先对于一个长度为n的有序数组a[n]，若n为偶数，则中位数为(a[n/2]+a[n/2-1])/2，若n为奇数，则中位数为a[n/2]，那么问题的关键就是找到a[n/2]和a[n/2-1]，然而这是在有序数组中的，那么换到无序的数组中，我们可以把问题转换为求数组中第n/2大的和第n/2+1的数，再一般点就是求一个无序数组中第k大的数。那么如何求第k大的数呢，我们可以先在数组中取一个值value，将数组划分为小于value的small，等于value的equal，大于value的big三个部分，分别记三个部分的元素个数为numS、numE、numB，若k if (a[i] equal[numE] = a[i]; numE++; } else { big[numB] = a[i]; numB++; } } if (k numE + numS)return selectK(big, numB, k-numS-numE); else return value; } int main() { srand((int)time(0)); int n; cin >> n; int *array = new int[n]; for (int i = 0; i